#include <bits/stdc++.h>
using namespace std;

/*
869. 重新排序得到 2 的幂
已解答
中等
相关标签
premium lock icon
相关企业
给定正整数 n ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。

如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。

 

示例 1：

输入：n = 1
输出：true
示例 2：

输入：n = 10
输出：false
 

提示：

1 <= n <= 109
*/

// 法一
class Solution {
public:
    /*
    error: call to implicitly-deleted default constructor of 'std::unordered_set<vector<int>>'
    5 |         std::unordered_set<vector<int>> powerOf2DigSets;

     std::vector 没有默认的哈希函数  因此自定义哈希
    */
    struct VectorHash {
        template <class T>
        size_t operator()(const vector<T>& v) const {
            size_t seed = v.size();
            for (auto& i : v) {
                seed ^= hash<T>()(i) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
            }
            return seed;
        }
    };

    bool reorderedPowerOf2(int n) {
        // 存储所有2的幂的数字组合
        std::unordered_set<vector<int>, VectorHash> powerOf2DigSets;
        for (int i = 0; i < 31; i++) {
            int powerOf2 = 1 << i;
            if (powerOf2 > 1e9)     break;
            vector<int> cnt(10, 0);

            int tmp = powerOf2;
            while (tmp > 0) {
                cnt[tmp % 10]++;
                tmp /= 10;
            }
            powerOf2DigSets.insert(cnt);
        }
        vector<int> countN(10, 0);
        while (n > 0) {
            countN[n % 10]++;
            n /= 10;
        }
        // 检查n的数字组合是否与某个2的幂的数字组合相同
        return powerOf2DigSets.count(countN) > 0;
    }

    bool isSameDigits(int n1, int n2) {
        vector<int> cnt1(10, 0);
        vector<int> cnt2(10, 0);

        while (n1 > 0) {
            cnt1[n1 % 10]++;
            n1 /= 10;
        }
        while (n2 > 0) {
            cnt2[n2 % 10]++;
            n2 /= 10;
        }

        return n1 == n2;
    }
};

// 法二
class Solution {
public:
    // 存储2的幂次方的数组，从2^0到2^32
    long long m[35] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536};
    // cnt数组用于记录每个2的幂次方中各个数字出现的次数，cnt[i][j]表示2的i次方中数字j出现的次数
    int cnt[35][10], ct[10]; 

    // 检查当前数字n的数字组成是否与某个2的幂次方的数字组成相同
    bool real(int id) { 
        for (int i = 0; i < 10; i++) {
            // 如果当前数字n中数字i的出现次数与2的id次方中数字i的出现次数不同，则返回0
            if (ct[i] != cnt[id][i]) return 0; 
        }
        // 如果所有数字的出现次数都相同，则返回1
        return 1; 
    }

    bool reorderedPowerOf2(int n) {
        // 初始化2的0次方和2的1次方的数字组成情况
        cnt[0][1] = 1; 
        cnt[1][2] = 1; 
        cnt[2][4] = 1; 
        cnt[3][8] = 1; 

        // 计算2的2次方到2的32次方，并记录每个2的幂次方中各个数字出现的次数
        for (int i = 1; i <= 32; i++) {
            m[i] = m[i - 1] * 2; 
            long long x = m[i]; 
            while (x) {
                cnt[i][x % 10]++; 
                x /= 10; 
            }
        }

        // 记录输入数字n中各个数字出现的次数
        long long nn = n; 
        while (nn) {
            ct[nn % 10]++; 
            nn /= 10; 
        }
        // 输出数字n中各个数字出现的次数，用于调试
        // for (int i = 0; i < 10; i++) cout << ct[i] << " "; 
        // 遍历所有2的幂次方，检查是否有与数字n数字组成相同的
        for (int i = 0; i <= 32; i++) {
            if (real(i)) return 1; 
        }
        // 如果没有找到匹配的2的幂次方，则返回0
        return 0; 
    }
};

// 法三
// 减少不必要的计算和空间占用
/**
 * 我们可以先对输入数字 n 进行排序，然后通过生成所有可能的 2 的幂次方，对每个 2 的幂次方的数字也进行排序，再直接比较排序后的结果，这样可以避免使用哈希表带来的复杂操作以及哈希冲突等问题，同时减少空间占用。
 */
class Solution {
public:
    bool reorderedPowerOf2(int n) {
        // 将n的各位数字提取到数组中并排序
        std::vector<int> digitsOfN;
        while (n > 0) {
            digitsOfN.push_back(n % 10);
            n /= 10;
        }
        std::sort(digitsOfN.begin(), digitsOfN.end());

        // 遍历所有可能的2的幂次方
        for (int i = 0; i < 31; ++i) {
            int powerOf2 = 1 << i;
            // 将2的幂次方的各位数字提取到数组中并排序
            std::vector<int> digitsOfPowerOf2;
            while (powerOf2 > 0) {
                digitsOfPowerOf2.push_back(powerOf2 % 10);
                powerOf2 /= 10;
            }
            std::sort(digitsOfPowerOf2.begin(), digitsOfPowerOf2.end());

            // 比较排序后的数字数组
            if (digitsOfN == digitsOfPowerOf2) {
                return true;
            }
        }
        return false;
    }
};